<?php
/**
 * @title 1713. 得到子序列的最少操作次数
 * @author start2004
 */

// ini_set("memory_limit", "128M");
// set_time_limit(60);

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param Integer[] $target
     * @param Integer[] $arr
     * @return Integer
     */
    function minOperations($target, $arr) {
        /**
         * @since 2021-07-27 arr的元素位置
         */
        $this->posArray = [];

        /**
         * @since 2021-07-27 统计位置
         */
        $lenArr = count($arr);
        for($i=0; $i<$lenArr; $i++){
            $this->posArray[$arr[$i]][] = $i;
        }
        echo count($arr), ", ", count($this->posArray); die();

        /**
         * @since 2021-07-27 目标数组, 目标数组长度
         */
        $this->target = $target;
        $this->targetLen = count($target);

        /**
         * @since 2021-07-27 匹配最大值
         */
        $max = self::find(0, 0);

        /**
         * @since 2021-07-27 最少操作次数
         * @return
         */
        return $this->targetLen - $max;
    }

    /**
     * @title 返回匹配最大值
     * @author start2004
     * @since 2021-07-27 Created
     *
     * @param int $i
     * @param int $minPos
     * @param int $lastPos
     */
    public function find($i=0, $minPos = 0){
        /**
         * @since 2021-07-27 target第一个元素能否找到符合位置
         */
        $findPos = false;
        $num = $this->target[$i];
        if(isset($this->posArray[$num])){
            /**
             * @since 2021-07-27 二分查找
             */


            foreach ($this->posArray[$num] as $pos){
                if($pos >= $minPos){
                    $findPos = $pos;
                    break;
                } else {
                    /**
                     * @since 2021-07-27 不需要移除, target每个元素互不相同
                     */
                }
            }
        } else {}

        /**
         * @since 2021-07-27 最后一个元素
         */
        if($i+1 == $this->targetLen){
            if($findPos === false){
                $max = 0;
            } else {
                $max = 1;
            }
        } else {
            /**
             * @since 2021-07-27 下个元素
             */
            $i++;

            /**
             * @since 2021-07-27 target[0]无法匹配
             */
            if($findPos === false){
                $max = self::find($i, $minPos);
            } else {
                /**
                 * @since 2021-07-27 上个元素不匹配
                 */
                if($lastPos == -1){
                    /**
                     * @since 2021-07-27 target[0]匹配, 不匹配
                     */
                    $max = max(self::find($i, $findPos+1)+1, self::find($i, $minPos));
                } else {
                    if($lastPos < $findPos){

                    } else {}
                }
            }
        }

        /**
         * @return
         */
        return $max;
    }
}

/**
 * @url http://127.0.0.1/leetcode/202107/2021.07.26_2.php
 */
$datas = [
    // [[5,1,3], [9,4,2,3,4]], // 2
    // [[6,4,8,1,3,2], [4,7,6,2,3,8,6,1]], // 3
    [[679616344,935342044,873684903,157591400,939467939,24039899,680497461,114415052,591225248,40859460,838724849,523660427,460597350,69221781,275345938,731680204,484351284,448633367,456925925,903109502,434381297,624978474,188009966,883719051,933856192,319121599,417112362,614799531,935872247,111538651,318179622,510055253,185715512,761609906,216067350,886336125,64260193,539999208,10719702,934633702,715686703,496642346,456814627,143587872,911243414,732141614,701898904,407246366,596371703,187511720,444034006,247039608,214093132,62996863,51066200,339105275,458280587,129959219,444704364,609478181,454870687,753432261,772704875,802151798,618249140,865304466,5409855,645039607,629213080,179843003,465289747,284879101,736132672,703955626,419233529,228987255,758274367,513652374,976566004,74279869,491023111,530183036,569025709,745132109,145059284,294329721,513640221,87616977,11848277,428846924,754114807,613879488,722886819,336916016,107462236,230169875,751872418,919446467,71689099,237561696,874667347,636830418,773101842,51275351,33168101,278638503,571880392,540037488,431644950,543689341,137167593,441383518,358517288,18793025,199173424,454163021,639577755,952178521,39183489,317553457,878225932,537612485,512203154,352071562,470861994,3124121,735983175,65713176,805318848,90841730,899144725,285992481,664057996,454263525,697246035,205774663,488056416,498487086,589351311,96995225,304375378,363770117,993028678,591039402,549117426,17778678,330169581,700085634,739389764,224272077,472288430,107640921,306435359,861805659,560348533,442578188,334482337,797943455,802160126,540552524,28683188,497326677,581649415,346514568,80314746,806733081,871311081,128211076,58106171,708193616,768746050,185500103,442864655,321147163,285720675,322911666,601008501,314838861,132794063,200192452,313268335,31523179,618677822,286890034,100247251,621814776,219980616,988493667,813488500,324346452,69219372,150995741,108814294,390794756,581669778,896992105,230067593,871800748,985819794,82213854,80465832,658815017,174104110,349418282,792339102,966164107,585271757,660693428,482362255,538709379,447942801,535811361,618378105,821401252,635004510,982020387,959084439,308379714,549769699,612938651,680278979,618137857,752617578,809175072,817019737,16406582,733050793,177921415,423515897,739015502,59224582,426243148,283940171,348627004,932699238,356958049,907949670,622134857,962042833,6237551,880398891,296963748,537794587,492060253,309246608,126080203,720071508,537128375,988621894,227849511,110394922,451220287,799390568,910460283,18423453,324106388,1495709,200016617,372041906,405006372,740488751,47788604,369698406,444763063,859917154,325981718,172544389,355514878,933021197,308193817,656246495,689105924,465610757,864921561,249327019,389096092,375950635,47726448,154751169,172954363,830762441,811464048,446073079,987649502,283362229,903754930,284501797,936129073,705260510,94866811,402681814,296271457,989343797,57069381,283564435,983766657,432764474,627877891,792432260,912733868,738435587,69984370,118903439,979567650,446541111,720648611,366769324,96811703,469491398,355199374,346562146,959563145,626937008,495056782,53805995,813937800,646270532,989987814,998799656,8058281,193960728,420568172,300085239,493984566,786364710,523864847,498239437,286864906,440902505,250085234,94801907,470220711,162329211,547791583,984070409,362861724,7551661,790119403,34488895,49263268,152449529,818624492,286195095,50339074,521363873,323554544,992776567,915066671,247977356,798986444,238757057,952812252,95143386,737397239,615308979,46220024,829106002,834455028,825111050,753923913,999069475,116698041,690356109,993379961,817048967,237502267,841503748,673149955,189644635,19222000,252489695,904534513,305647808,401506609,453907258,871181085,846248930,941011620,334333115,525160015,384216536,615200031,445638887,538643673,954291585,558822724,861612389,87263788,83806411,759572861,300186984,199780473,632620416,364185280,170392842,677904611,621834411,926775730,674917314,708090484,603461070,565414453,808525606,902880387,334428715,925515429,18181955,510042294,23209989,851501103,316903651,738662578,187377337,595809096,743503713,161651541,648933721,544197547,815047346,853317498,985364195,433160305,234777575,108902537,116330064,861620477,574310947,796777365,20931651,792285533,38831659,855068775,259297094,174907722,236688404,682492001,903913985,495706626,70031205,375026474,176920566,781548845,18839443,410825715,565445627,327003754,793563315,877408308,424963042,649532666,289954230,691068876,345692704,296513925,231056662,747201760,619467549,399751503,156562665,710517922,455421134,420695258,729764878,954712721,840535037,880706733,340653753,716344683,895795628,844705692,873372448,763693764,767231888,753492265,499610069,428352780,73503180,8470585,349715099,459234998,604703483,211621153,91184879,254408756,516762984,693435718,636257321,55731536,727052395,765437103,55220854,599426199,180532331,662200079,912514271,143710036,919504594,892555873,262554442,467196726,230032721,597757439,144070703,174810427,386823202,820527547,445305536,910694345,409747701,19143635,621213450,938234527,490897893,519027767,602996121,844366883,296159851,920509758,839252488,53350363,846917292,216888540,890953107,678331999,630330991,551673695,180371945,739008539,182366756,652809240,171052710,597114458,135187679,889069419,760400943,87166873,453137353,572175003,10299606,705352384,355320502,393332626,54935490,10767557,421205324,45503804,45679471,942394630,539292603,50606113,914622192,496277804,272282524,147914675,524898716,716542423,16942946,685124105,991443769,21836853,892902353,176803919,135044350,401914233,270952072,607008343,286886678,240411346,974653384,404828016,355484127,259736111,484748997,858531851,644782983,182815647,755684140,561462241,686157203,892138195,868213973,720484308,947095627,684394944,452960964,788196100,210729048,868967114,813891543,86848471,592644326,96456748,401476285,502615450,366283949,774710099,524392148,93777759,177874740,700876827,646321202,362622859,735758851,739573855,941924266,962164766,334190867,943683092,224662922,813826465,684126188,853154372,684128600,39104987,29304258,409188622,850900980,589585980,455368668,863719002,1626797,468295046,382918767,449753442,16231798,873913502,182554253,164814784,937460605,541229375,165052360,107492464,210347487,817684774,939467878,793439273,412232323,674229690,279303256,904800738,328481777,891724358,37099273,61905217,860905192,661240520,583080730,119277430,375784325,519806009,948178959,676215046,342722767,346421556,580427214,696521370,638707729,371403565,887610768,790370042,888950644,803350056,248236640,22142605,214149797,593605803,980031224,167764092,632406554,814864095,941151087,66563813,817100286,795573999,772136368,422672826,894803400,498698864,139748154,280075699,236916150,867656744,460915016,300438998,589464189,288664244,292577923,456571267,932367443,733403619,184308904,431710347,781509775,23826291,949141790,637363837,844344485,822740127,371315198,126022409,664693711,475692859,544675692,550944834,557082226,917286218,616229857,360847950,796849414,528922412,810921647,39459866,668531880,582706729,692160590,538613122,157743684,308422738,737431568,209233777,634851709,799050870,714182212,213816046,718155293,88132599,446914798,135411883,713243437,848741895,543410474,74989849,603805545,104785786,908681748,563775641,585169691,434945907,290086371,490075503,61362138,147037457,559121661,388150450,736013172,353770048,241014915,13388396,961700437,526032099,887878126,425103243,566694608,732290207,625300332,862632518,341182464,719436179,93213999,680138708,897573403,770649188,616696962,864271686,991811087,910310974,587361346,128075360,942376183,405213756,325175788,577013015,407477997,271278486,377280991,942235348,136194238,280100759,861657893,215910447,345497273,169771573,991775651,853773108,956816643,389327503,77039364,106854506,617045601,512690686,770403897,746112731,328010561,349924118,148460015,723633810,41229124,364887084,461824753,806459450,431746948,20574293,733760809,743853291,587950807,972902871,398167457,67863334,452291447,491945952,543552690,495549063,68853136,50151867,40015396,654915633,857015419,937206404,577469387,808263982,751400782,876999219,210727034,169775819,825219162,952206362,890585553,1398921,796296259,270777726,299868415,192685383,932224052,339721827,768394151,509753149,925750194,836069526,372573895,85346429,220201338,369715826,441116894,598563593,953370679,98535865,899954743,907409456,264195363,455698616,209889299,665611000,61206725,540112704,239361167,219745267,500126899,314386678,848317767,97938943,36908101,133112076,604379070,551655121,914311147,341073707,240618232,392331731,775610860,733512250,340942326,598759993,458403508,507448931,218155764,62198786,146215708,73766737,933755115,978683586,837460924,903035766,51573872,6419887,993922300,121913306,645123611,852119946,53628594,506540925,563202870,10436283,359277024,815665200,503038298,874581604,638121389,408293763,263755490,682783306,19855591,968806442,46881061,658802180,501084823,366613675,27990807,708069021,298403530,636508550,521083248,100264555,289161569,328148958,570537358,334922804,638621136,530841902,414586602,147580357,857436404,412394581,700427916,370361001,818772607,501701009,776271941,745006104,944421509,444994294,640462147,369633680,502381390,259924242,530873441,205601961,383809539,594236423,514560762,167375528,809258227,996370528,275212011,185021368,379214081,953104549,291550287,82655963,970265727,903169247,416230493,650653249,787440957,891413913,827293568,259032850,111324075,913850718,844042021,89992596,429931965,313016282,786170052,79553301,578239240,38240518,871107005,82721597,780181188,5909958,868755610,968410688,557847784,765152965,981387362,798476006,800629568,771028880,249118945,45081092,509221792,860245949,435582166,711730372,624433419,870413186,171823330,812428545,625399616,997448225,72743748,55576389,288652389,254361029,24765287,52211871,216603318,804726227,510045886,703893319], [253459048,805318848,817019737,763693764,237502267,903035766,238757057,1451203,139748154,612938651,231056662,410825715,700876827,768394151,231945693,790628373,713780158,512690686,903007536,904603390,173357998,708193616,972921438,616120762,919777425,213287690,806459450,311779298,560890616,668531880,305647808,412659029,888950644,956816643,966164107,711116308,891413913,68130062,834455028,82721597,980049456,944421509,446034857,793447357,263755490,732141614,658815017,941924266,260648506,53350363,69219372,625663224,290086371,366769324,135044350,776271941,776271941,684394944,842467360,244949399,743503713,390277804,372041906,818772607,46881061,160534152,591225248,402681814,356009528,938234527,95143386,564980340,52211871,97724722,469491398,911243414,669901230,133112076,630330991,390794756,419233529,184335924,50339074,625399616,18423453,577469387,679616344,874667347,73503180,874667347,585271757,625396282,412232323,370361001,458377331,24765287,371315198,523864847,407776525,334190867,162329211,82721597,93084107,219980616,19143635,348627004,93777759,359277024,405006372,76881732,936129073,236688404,775610860,937206404,95485863,822592805,736013172,194043727,544675692,302641685,53805995,870413186,664291656,735983175,803350056,303990675,616696962,87263788,47258376,662200079,95485863,776271941,576312021,544510801,680278979,594236423,543689341,968410688,543410474,648933721,732290207,93777759,743361157,469491398,903754930,27990807,368066412,262554442,325752860,913850718,589464189,290086371,858531851,286890034,383552280,53628594,752026755,164003753,171007141,147580357,89262351,237561696,308422738,484351284,572170506,812946749,132794063,931117827,948178959,49263268,194239132,438148907,205774663,199780473,178930695,421205324,428364056,655063370,453137353,357065145,349418282,69221781,349924118,656246495,848317767,18181955,260648506,487352455,891413913,634851709,910485534,614799531,174810427,82213854,318449461,880706733,473582150,165417755,308193817,439819225,892555873,215910447,424963042,560890616,868967114,375950635,205601961,616120762,69273824,107640921,656352024,286195095,239361167,650119012,787440957,157171961,652809240,713780158,931117827,245284664,808263982,199780473,795533590,21836853,28469522,135187679,880398891,980087975,517638056,216067350,802160126,609085111,887610768,717115397,899144725,308091092,578239240,409188622,444763063,37141560,660693428,36153162,20931651,102860452,975012394,899144725,93777759,632406554,641832228,216007565,324346452,497326677,216603318,339105275,443790324,842152499,676955264,645092501,790119403,355484127,497326677,180371945,308379714,561773216,285992481,349715099,438031860,401914233,216888540,19222000,716344683,887878126,407246366,881905054,452960964,614799531,70031205,626937008,910310974,440393776,352071562,523660427,796777365,525160015,974653384,67863334,334428715,644782983,509221792,259778813,661240520,998799656,1398921,848847305,867656744,839252488,341967339,513652374,327978682,512690686,167053817,530841902,362304259,244949399,192439706,711730372,508257930,770649188,43605066,820008493,903109502,530183036,463532583,147037457,330169581,682783306,863719002,700427916,23826291,453137353,978683586,980087975,352071562,926775730,560348533,931965620,47726448,561462241,797943455,954712721,911012460,314838861,278638503,220201338,674229690,853154372,887878126,839252488,617045601,942235348,68502347,355514878,214149797,992609906,874421843,728743665,819099056,22382404,61206725,635899153,503038298,844344485,720071508,829763225,55731536,509753149,364887084,697246035,604379070,672231771,37099273,456571267,597114458,904534513,645039607,362304259,874667347,80601557,626937008,325981718,390794756,55731536,94866811,379214081,64559469,849001607,492060253,910485534,868213973,607799148,672396020,864271686,752285500,563681679,985364195,691068876,322911666,658802180,684825351,994392381,91184879,524392148,189644635,670714736,500126899,758274367,968410688,171052710,630330991,896992105,848847305,860905192,329045579,700876827,185021368,365613561,165417755,172593459,396882536,338923836,614799531,225872272,161192119,460597350,424963042,899954743,171823330,108902537,722886819,753641209,94866811,974653384,676215046,697246035,173115563,735393422,94801907,682492001,89262351,798286602,82721597,658802180,817684774,126080203,697618876,123900819,138032401,502381390,815047346,708069021,736013172,664291656,38240518,926073824,73503180,547214609,863849652,443177593,827178385,505217696,358066304,200734540,739573855,644325052,89992596,658725310,926264818,405213756,384891661,497689408,325752860,247721373,962164766,751400782,72743748,174104110,404828016,993922300,376376259,510042294,561773216,230801026,966164107,590244423,910460283,308422738,968806442,761609906,317553457,640462147,825536240,838724849,566548078,586896585,630330991,473588911,757517914,241014915,3124121,143710036,146159322,753923913,227849511,390277804,24039899,629213080,593605803,477368342,69273824,460597350,861657893,215910447,164003753,684126188,815047346,286886678,509753149,396440673,454261041,821294886,434381297,815047346,407477997,690356109,69984370,470220711,280932896,188265613,768746050,467196726,854999734,455698616,70442613,897573403,358678477,328148958,211621153,495706626,708069021,454263525,868318032,664291656,680278979,962042833,230841368,284879101,790119403,897573403,887878126,556459869,393332626,892555873,285992481,230032721,491945952,56806415,679616344,751078701,739573855,407477997,861805659,146215708,540552524,322911666,167375528,385653330,809258227,574310947,640531741,740142409,689105924,577013015,559121661,981464175,560374411,604379070,167053817,614919685,493984566,761609906,6419887,918512640,382918767,349418282,825219162,638707729,355320502,334428715,402725208,858531851,739008539,613550243,786170052,19333973,781448449,47258376,401506609,902880387,93777759,887878126,230032721,589351311,654915633,38240518,39459866,544675692,264807159,953104549,617045601,264807159,551655121,434945907,418168118,879203267,635899153,635004510,699104219,625399616,903754930,328148958,768746050,868755610,18423453,509753149,296963748,85346429,10719702,877408308,376847961,13808429,205882694,294267134,661240520,787440957,438258312,507448931,670714736,409188622,355199374,913850718,184308904,919777425,676064312,263770866,313268335,523589939,494785020,5909958,59224582,57069381,855068775,484748997,729764878,476143656,225872272,177081815,82721597,514560762,899366027,577469387,486215973,230841368,213816046,910310974,371315198,503038298,1495709,620214723,407477997,933856192,86936375,300438998,438010003,727052395,993379961,622134857,288664244,528922412,171007141,10436283,613879488,696521370,540552524,257641176,413881678,10767557,993922300,264807159,854999734,861620477,303990675,918512640,726727208,272282524,52211871,903169247,625396282,69219372,84989887,658725310,33525380,700085634,184308904,87166873,36843104,461994218,215910447,291702631,434945907,575898133,429931965,189644635,479164555,728743665,346421556,596921429,490897893,796849414,558822724,715686703,445638887,676064312,598563593,173115563,393332626,6237551,87646762,405213756,443177593,733760809,837460924,711116308,152956250,328148958,300186984,463252510,220778980,945691530,31835048,560482424,39104987,61206725,819081715,571880392,590244423,733403619,3124121,739389764,524392148,318179622,751078701,55731536,580427214,793447357,609085111,53805995,802151798,18776721,180371945,626937008,808263982,975012394,33168101,858843396,594236423,479164555,521083248,758638449,999482291,563681679,880398891,862632518,108902537,800145367,263770866,419233529,108902537,7551661,560348533,714182212,565445627,313016282,340653753,813488500,680802470,231056662,954291585,988621894,302972031,723633810,448633367,157743684,116698041,250085234,711730372,772136368,955651570,590559110,172954363,172544389,497326677,812946749,772136368,498698864,874581604,920509758,740142409,689105924,19143635,13808429,728743665,636257321,888950644,853154372,889069419,820527547,351449356,808619853,574310947,22385085,655063370,890585553,808525606,636830418,645123611,539004162,21020413,867656744,390794756,147580357,919627134,738662578,918512640,139748154,690356109,889062889,147037457,382918767,684128600,200192452,291550287,82655963,288254152,39104987,45081092,231945693,528657049,453907258,894803400,765152965,16231798,966164107,846917292,404828016,456814627,224272077,740142409,316330070,560482424,275345938,603805545,479164555,534639505,765838810,355484127,18181955,878225932,283362229,523589939,991775651,772704875,278638503,890953107,904800738,252040939,128019752,249118945,224662922,491023111,736013172,50151867,452960964,680278979,851501103,864921561,676215046,500126899,991775651,899366027,119277430,537128375,939467878,720361577,223755018,1451203,313268335,680802470,817237250,756338458,438383162,425103243,598759993,442578188,283362229,846917292,581649415,581649415,839252488,300438998,903913985,138170186,701898904,825219162,787440957,439819225,843321179,796296259,70442613,964503832,655283223,71689099,413881678,260648506,999069475,665611000,880706733,674229690,157591400,61905217,91184879,403753263,86848471,984070409,584278454,184308904,417112362,259297094,585169691,927309993,33525380,925750194,339105275,411190389,843321179,627011695,61206036,945214848,30773497,426243148,366283949,577013015,39104987,846917292,658802180,438258312,166344099,296513925,470220711,853773108,98535865,369698406,137167593,401506609,627011695,338923836,453907258,535811361,259297094,733760809,798286602,360847950,199780473,441383518,932224052,470220711,50606113,167764092,137167593,753492265,460597350,675046518,352071562,714460512,458280587,308091092,848317767,166344099,815047346,621834411,34488895,695495747,885551334,817684774,298403530,823105211,16942946,638121389,87646762,135411883,804726227,453907258,313016282,556605017,746112731,18793025,889069419,337386982,684126188,390794756,223755018]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->minOperations(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
